#ifndef GRAPH_H
#define GRAPH_H

#include <iostream>
#include <vector>
#include <stdio.h>
#include "string.h"
#include <string>
#include <cmath>
using namespace std;

class graph
{
 private:
  int infinite = 99999999;
  
  struct link_info
  {
    int node_id;
    double length;
    
    link_info(int _id, double _length)
    {
    	node_id = _id;
    	length = _length;
    }
  };

  struct graph_node
  {
    int node_id;
    vector<link_info*> edges_table;
    vector<double> edges_matrix;
  };

    vector<graph_node*> node_list;
    
 public:
  int total_node = 0;

  void set_node(int num)
  {
    total_node = num;
  }
  
  void initial(int total_node,bool mode)
  {
    for(int i = 1; i <= total_node; i++)
      {
	graph_node* newnode = new graph_node();
	newnode->node_id = i;
	node_list.push_back(newnode);
	if(mode)
	  {
	    for(int k = 0; k < total_node ; k++)
	      {
		if(i == k+1)
		  newnode->edges_matrix.push_back(0);
		else
		  newnode->edges_matrix.push_back(infinite);
	      }
	  }
      }
  }

  void single_input(int id_1,int id_2,double length,bool mode)
  {
    if(!mode)
      {
	link_info* link_input = new link_info(id_2,length);
	node_list[id_1-1]->edges_table.push_back(link_input);
      }
    else
     node_list[id_1-1]->edges_matrix[id_2-1] = length;     
  }
  
  void stream_input(bool mode)
  {
    int id_1,id_2;
    while(1)
      {
	double length = 1;
	cin >> id_1;
	getchar();
	cin >> id_2;
	char judge;
	judge = getchar();
	if(judge == '\n')
	  {
	    single_input(id_1,id_2,length,mode);
	      continue;
	  }
	cin >> length;
	single_input(id_1,id_2,length,mode);
	judge = getchar();
	if(judge == 's')break;
      }
  }
  
  void input(bool mode)
  {
    cout << "Number of nodes:";
    cin >> total_node;
    initial(total_node,mode);
    stream_input(mode);
  }

  void ListVertexes()
  {
    for(int i = 0; i < node_list.size() ; i++)
      {
	cout << node_list[i]->node_id << " " << endl;
      }
  }

  void ListEdges(bool mode)
  {
    if(!mode)
      {	
	for(int i = 0; i < node_list.size() ; i++)
	  {
	    for(int k = 0; k < node_list[i]->edges_table.size() ; k++)
	      {
		cout << "(" << node_list[i]->node_id << ","
		     << node_list[i]->edges_table[k]->node_id << ","
		     << node_list[i]->edges_table[k]->length << ")" << endl;
	      }
	  }
      }
    else
      {
	for(int i = 0; i < node_list.size() ; i++)
	  {
	    for(int k = 0; k < node_list.size() ; k++)
	      {
		if(node_list[i]->edges_matrix[k] == infinite)continue;
		cout << "(" << i+1 << "," << k+1 << ","
		     << node_list[i]->edges_matrix[k] << ")" << endl;
	      }
	  }
      }
  }
  
  void Bellman_Ford()
  {
    int flag = 0;
    int dis[total_node],judge[total_node];
    int ite = total_node;
    for(int i = 1; i < total_node; i++)
      dis[i] = infinite;
    dis[0] = judge[0] = 0;

    for(int i = 1; i < total_node ; i++)
      judge[i] = infinite;
    
    while(--ite)
      {
	for(int i = 0; i < total_node; i++)
	  {
	    for(int j = 0; j < node_list[i]->edges_table.size(); j++)
	      {
	        int _id = node_list[i]->edges_table[j]->node_id - 1;
		if(dis[_id] > dis[i] + node_list[i]->edges_table[j]->length)
		{
		  dis[_id] = dis[i] + node_list[i]->edges_table[j]->length;
		}
	      }
	  }
      }
  
   /* for(int i = 0; i < total_node ; i++)
    {
      if(dis[i] == infinite)
	{
	  cout << "inf ";
	  continue;
	}
      cout << dis[i] << " ";
    }*/
  }

  void Random_Graph(int Num_E)
  {
    int ava_node = total_node * (total_node-1);
    for(int i = 0; i < total_node ; i++)
      {
	for(int j = 0; j < total_node ; j++)
	  {
	    if(i == j) continue;
	    if(((double)(rand()%1001)/1000) <= (double)Num_E/(double)ava_node--)
	      {
	        link_info* newedge = new link_info(j+1,rand()%1001-500);
		node_list[i]->edges_table.push_back(newedge);
		Num_E--;
	      }
	    else
	      ;
	  }
      }
  }

  double start,end,dur;
  
  void clear()
  {
    for(int i = 0; i < total_node ; i++)
    {
       while(node_list[i]->edges_table.size())
       {
	  node_list[i]->edges_table.pop_back();
       }
    }
  }
  
  void test_Vsame()
  {
    set_node(1000);
    initial(1000,0);
    for(int i = 10; i <= 400 ; i+=10)
      {
	Random_Graph(1000*i);
	start = clock();
	Bellman_Ford();
	end = clock();
	dur = (end - start)/1000000;
	printf("%6d %6lf\n",1000*i,dur);
	clear();
      }
  }

  void test_Esame()
  {
    for(int i = 1050 ; i <= 2000 ; i+=50)
      {
        set_node(i);
	initial(i,0);
        Random_Graph(400000);
	start = clock();
	Bellman_Ford();
	end = clock();
	dur = (end - start)/1000000;
	printf("%4d %6lf\n",i,dur);
	clear();
      }
  }
	

};
#endif
  
